//
//  MergeSort.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/3.
//

import Foundation

/// 归并排序
/// - Parameter array: 数据
/// - Returns: 归并排序
func mergeSort<E>(_ array: [E]) -> [E] where E: Comparable {
    guard array.count > 1 else {
        return array
    }
    let middle = array.count / 2
    let left = mergeSort(Array(array[..<middle]))
    let right = mergeSort(Array(array[middle...]))
    print("Before merge: \(left + right)")
    let merge = merge(left, right)
    print("After merge: \(merge)")
    return merge
}

func merge<E>(_ left: [E], _ right: [E]) -> [E] where E: Comparable {
    var leftIndex = 0
    var rightIndex = 0
    var result: [E] = []
    while leftIndex < left.count &&
            rightIndex < right.count {
        let leftElement = left[leftIndex]
        let rightElement = right[rightIndex]
        if leftElement < rightElement {
            result.append(leftElement)
            leftIndex += 1
        } else if leftElement > rightElement {
            result.append(rightElement)
            rightIndex += 1
        } else {
            result.append(leftElement)
            leftIndex += 1
            result.append(rightElement)
            rightIndex += 1
        }
    }
    if leftIndex < left.count {
        result.append(contentsOf: left[leftIndex...])
    }
    if rightIndex < right.count {
        result.append(contentsOf: right[rightIndex...])
    }
    return result
}
